1. Field of the Invention
The present invention relates to digital image analysis and mapping. More specifically, the present invention relates to edge detection and road network tracking in aerial digital images.
2. Description of the Related Art
Aerial images are produced by cameras located in aircraft or other flying machines and from orbiting satellites. Such cameras are typically pointed downward and are used to capture images of the Earth's surface. While photosensitive film and chemical processing have been employed to capture images in the past, modern aerial imaging systems typically employ digital imaging sensors that output digital image files. The digital image files produced by digital imaging sensors can be transmitted by radio communications or through transportation of digital data storage media. The file structure typically includes a plurality of pixels that are located in two dimensions and that comprise data reflecting the electromagnetic energy detected at each particular pixel location. In typical applications, the aerial image files are used to analyze Earth surface characteristics, both natural and man-made.
In the past, most aerial imaging systems were sensitive in the panchromatic, visible, spectrum. Modem imaging sensors have been deployed that are sensitive in the near infrared band, and that are monochromatic in certain narrow bands such as the green or red bands. Certain imaging sensors are sensitive in plural bands. In the case where an imaging sensor is sensitive in a single band, then the digital image file comprises a single data field indicating the magnitude of the energy in that band for each pixel in the file. In the case where a sensor is sensitive in plural bands, then each pixel comprises a vector with data indicating the magnitude of energy in each of the plural bands of sensitivity.
Regarding the use and application of the imaging data gathered by aerial imaging systems, the applications are many and varied. Some applications are mapping, topography, or weather related. Some are directed to industrial characteristics, natural resource management and trends over time. Of course, some applications involve the military and strategic interests of nations. One particular application is the mapping of roads. While human analysis has been employed to map roads from aerial images, the modern trend has been toward automated road mapping, thus greatly expediting and lowering the cost of the process of road detection and mapping from aerial image files. Automated road mapping has been comprised of two general steps. First is analyzing plural subsets of the pixels in a given image to identify certain characteristics of each subset that are consistent with those expected from a road structure. Second, is an analytical process of tracking road characteristics across pixel subsets to identify the path of a roadway through the image.
Of course, those skilled in the art appreciate that roadway mapping is analogous to structural mapping of a variety of other items in digital imagery. More generally stated, accurate edge and line (hereinafter referred to generically as “edge” or “edges”) orientation is important in cartographic applications, road extraction from aerial imagery, medical image processing, techniques for grouping labeled pixels into arcs and then segmenting the arcs into line segments, edge linking and other tasks requiring curvilinear features such as fingerprint processing, and others.
The characteristic that has typically been extracted from a road structure image in the prior art has been the detection of an edge or line in the pixel field. Essentially, a subset of pixels are analyzed to detect contrast changes, which are changes in adjacent pixel magnitudes, and, a direction of the edge or line is extracted. The direction, or orientation, has been determined using a compass type directional filter. A compass filter may be an implementation of a finite impulse response filter in a digital signal processor that outputs a filter response for each feasible orientation, given the pixel map of the given pixel subset. Pixel maps applied in the prior art have typically been three-by-three pixel areas or five-by-five pixel areas. Given a three-by-three pixel map, the feasible orientations are zero, π/4, π/2, 3π/4, and π radians. Of course, the orientations ranging from π to 2π radians mirror those in the 0 to π radian range. Typical methods used to compute the orientation value for a compass type of directional filter set are presented in R. Haralick and L. Shapiro, Computer and robot vision; Vol. 1, Addison-Wesley, 1992, and, A. Jain, Fundamentals of digital image processing, Prentice-Hall, 1989. Orientation estimates obtained by using compass type directional filters are inherently inaccurate, due to the quantization of the orientation values into ranges specified by the pixel map size and number of directional filter responses employed.
As noted above, modern aerial imaging systems provide multi-spectral output vectors for each pixel. Analysis of such data requires edge/line analysis for each band and a fusing of the processed data to determine the net edge/line magnitude and orientation. The prior art methods of doing this do not handle the multi-spectral images, or require segmentation-based highly complex operations in order to calculate line/edge strengths.
Despite the number of different approaches that have been proposed for edge and line detection, the accurate estimation of the edge orientation has only been marginally investigated. Most methods such as derivative approaches using linear filtering, mathematical morphology, Markov fields, and surface models, concentrate only on the accurate localization of the edge and its immunity to noise, but not the precise estimation of the edge orientation. Part of the problem with the prior art is that it was designed for a single energy band image. When plural energy bands of data are available, the prior art merely fuses the estimates from each band with an arithmetic averaging process.
Having extracted the edge/line magnitude orientation from plural pixel maps, the second operation in roadway mapping process is to track the edge through the plural image subsections to produce a useful map of the road path. Most prior art algorithms for extraction of road networks are based on edge linking and template matching techniques. Such techniques are described in “An Unbiased Detector of Curvilinear Structures” by C. Steger, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. PAMI-20, no. 2, pp. 113-125, 1998; “An Unsupervised Road Extraction Algorithm for Very Low-Resolution Satellite Imagery” by F. Porikli and T. Keaton, 1st Intl. Workshop on Pattern Recognition in Remote Sensing(PRRS), Andorra, Andorra, 2000, and “Cooperative Methods for Road Tracking in Aerial Imagery” by D. M. McKeown and L. Cooper, in Proc. IEEE Computer Vision and Pattern Recognition(CVPR), pp. 662-672, 1988. These techniques were mainly developed to deal with low-resolution imagery. However, the latest generation of satellites provide high resolution imaging that has about twenty to thirty times the resolving power. With higher resolution data, there are new challenges, such as shadows across the roadway, trees on a road edge, cars, so it is more complex.
The prior art primarily used a Markov (chain to model intensity values of pixels along a roadway. Also, the prior art Markov chain did not adapt well to changes in road surface color intensity (asphalt to concrete, etc.). Although some prior art techniques that have been developed to extract road networks from aerial imagery may be modified to deal with high resolution satellite imagery, the road networks present in high resolution satellite images are much more complex. This has created an environment where the prior art algorithms are unable to extract all the useful information available in the higher resolution imagery.
As mentioned above, high-resolution imagery road networks present more details on the roads such as lane markings, vehicles, shadows cast by buildings and trees, overpasses and changes in surface material, which make the extraction of road networks a much more complicated problem. As a result, most existing algorithms are not suitable to process high-resolution imagery. In addition, most existing algorithms are deterministic and model-free techniques, which is another reason why they can't handle the variations of road networks presented in high resolution-imagery.
In “Automatic Finding of Main Roads in Aerial Images by Using Geometric-Stochastic Models and Estimation” , by M. Barzohar and B. Cooper, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 18, no. 7, pp. 707-721, 1996, Barzohar and Cooper proposed a geometric-stochastic model of roads for finding main road networks, but this model is not optimal for two reasons. First, the model was developed to model roads in low-resolution imagery, hence it focused on modeling road edges using intensity variations. Second, the model was developed for road finding using dynamic programming. In order to apply dynamic programming in road finding, some unpractical assumptions have to be imposed into the model.
The extraction of road networks from high resolution satellite images requires a very different methodology from that used to extract roads from low resolution satellite images. In low resolution satellite images, the width of roads typically ranges from one pixel to five pixels and extraction of road networks is equivalent to detection of lines or detection of linear structures. However, with high-resolution images, the road-width can very considerably and additional variations are present such as lane markings, vehicles, shadows cast by buildings and trees, overpasses and changes in surface material. These variations make the extraction of road networks a much more complicated problem.
Thus there is a need in the art for a system and method for line and edge detection and structural detail mapping in digital imagery.